package com.biancheng.biancheng.biancheng3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和 {
    public static void main(String[] args) {
        三数之和 ff = new 三数之和();
        List<List<Integer>> list = ff.threeSum(new int[]{-1,0,1,2,-1,-4});
        System.out.println(Arrays.toString(list.toArray()));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        // 双指针，计算两数之和的基础上将target设置为-nums[i],然后计算left和right
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length <= 2) return res;
        Arrays.sort(nums); // 先排序

        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue; //去重, 用过一次的数字不能用第二次
            int target = -nums[i];
            int left = i+1, right = nums.length-1;
            while(left < right){
                if(nums[left] + nums[right] == target){
                    res.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right]))); //将数组转化为list，省去add过程
                    // 先进行加减操作
                    left++;
                    right--;
                    // 然后去掉重复的，如[-2, -1, -1, -1, 3, 3, 3]
                    while(left < right && nums[left] == nums[left-1]) left++;
                    while(left < right && nums[right] == nums[right+1]) right--;
                }else if(nums[left] + nums[right] < target){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return res;
    }



}
